package com.lw.leetcode.binary.a;

/**
 * 面试题 10.05. 稀疏数组搜索
 *
 * @Author liw
 * @Date 2021/5/10 13:17
 * @Version 1.0
 */
public class FindString {

    public static void main(String[] args) {
        FindString test = new FindString();
        String[] arr = {"DirNnILhARNS hOYIFB", "SM ", "YSPBaovrZBS", "evMMBOf", "mCrS", "oRJfjw gwuo", "xOpSEXvfI"};
        // ["DirNnILhARNS hOYIFB", "SM ", "YSPBaovrZBS", "evMMBOf", "mCrS", "oRJfjw gwuo", "xOpSEXvfI"]
        //"mCrS"
        int mCrS = test.findString(arr, "mCrS");
        System.out.println(mCrS);
    }

    public int findString(String[] words, String s) {
        int st = 0;
        int end = words.length - 1;
        while (st <= end) {
            int m = st + ((end - st) >> 1);
            while ("".equals(words[m])) {
                m++;
                if (m > end) {
                    m = st + ((end - st) >> 1);
                    while ("".equals(words[m])) {
                        m--;
                        if (m < st) {
                            return -1;
                        }
                    }
                }
            }
            if (words[m].compareTo(s) == 0) {
                return m;
            }
            if (words[m].compareTo(s) > 0) {
                end = m - 1;
            } else {
                st = m + 1;
            }
        }
        return -1;
    }

}
